//移动0:LC283
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
      int nonZero = 0;
      int n = nums.size(),cur = 0;
      while(cur < n)
      {
        if(nums[cur] != 0)
        {
          ::swap(nums[cur],nums[nonZero++]);
        }
        cur++;
      }
    }
};

//盛最多水的容器-LC11
class Solution {
public:
    int maxArea(vector<int>& height) {
      int res = 0;
      int n = height.size(),left = 0,right = n-1;
      while(left < right)
      {
        int volume = min(height[left],height[right]) * (right - left); //高度*宽度
        res = max(volume,res);
        //缩小区间,宽度肯定是在减小的，尽量让高度更大 => 值小的移动
        if(height[left] > height[right]) right--;
        else left ++;
      }
      return res;
    }
};


//三数之和
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
      sort(nums.begin(),nums.end());
      int n = nums.size();
      vector<vector<int>> ans;
      for(int i = 0;i<n;)
      {
         //固定一个数nums[i],然后在后续的范围里面找是否有两个数的和为-nums[i]
         //如果找到了,那么这三个数凑起来和就是0
         int left = i+1,right = n-1,target = -nums[i];
         while(left < right) //区间内至少要有两个元素
         {
            int sum = nums[left] + nums[right];
            if(sum > target) 
              right--;
            else if(sum <target)  
              left++;
            else 
            {
              ans.push_back({nums[i],nums[left],nums[right]});
              //对left和right指向的元素进行去重
              left++,right--;
              while(left < right && nums[left] == nums[left-1]) left++;
              while(left < right && nums[right] == nums[right+1]) right--;
            }
         }
        //对i指向的元素进行去重
        i++;
        while(i < n && nums[i] == nums[i-1]) i++;
      }
      return ans;
    }
};

// 四数之和
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        int n = nums.size();
        for(int i = 0;i<n;) //固定一个数a
        {
            for(int j = i + 1 ; j < n;) //固定一个数b
            {
                int left = j + 1,right = n - 1; //在[left,right]区间求两数之和为target - a - b
                long long aim = (long long)target - nums[i] - nums[j]; //防止溢出风险
                while(left < right)
                {
                    int sum = nums[left] + nums[right];
                    if(sum > aim)
                        right--;
                    else if(sum < aim)
                        left++;
                    else 
                    {
                        ans.push_back({nums[i],nums[j],nums[left],nums[right]});
                        //对left和right指向的元素进行去重
                        left++,right--;
                        while(left < right && nums[left] == nums[left - 1]) left++;
                        while(left < right && nums[right] == nums[right + 1]) right --;
                    }
                }
                //对j指向的元素进行去重
                j++;
                while(j < n && nums[j] == nums[j-1]) j++;
            }
            //对i指向的元素进行去重
            i++;
            while(i < n && nums[i] == nums[i-1]) i++;
        }
        return ans;
    }
};

//有效三角形的个数 
//暴力解法O(N^3)
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
      sort(nums.begin(),nums.end());
      //两边之和大于第三边
      int res = 0;
      int n = nums.size();
      for(int i = 0;i<n;i++)
      {
        if(nums[i] == 0) continue;
        for(int j = i + 1;j < n ; j++)
        {
          for(int k = j+1;k<n;k++)
          {
            if(nums[i] + nums[j] > nums[k])
              res++;
          }
        }
      }
      return res;
    }
};

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
      sort(nums.begin(),nums.end());
      //两边之和大于第三边
      int res = 0,n = nums.size();
      for(int i = n-1;i>=2;i--) //确定一条最大的边
      {
        int left = 0,right = i - 1;
        while(left < right) //区间内至少要有两个数
        {
          if(nums[left] + nums[right] > nums[i])
          {
            res += right - left ;
            right--;
          }
          else 
          {
            left++;
          }
        }
      }
      return res;
    }
};
